ЛЕКЦИЯ 1
Основы алгоритмизации.
Алгоритмы. Схемы алгоритмов. Начальные сведения о программах.
Алгоритм и программа
Алгоритм - это последовательность действий, которые необходимо выполнить, чтобы решить поставленную задачу.
Программа же представляет собой набор команд на языке, понятном исполнителю, реализующий некоторый алгоритм. В нашем случае исполнителем является компьютер, а языком программирования будет язык высокого уровня Pascal. Любой язык высокого уровня удобен только человеку, пишущему или отлаживающему программу, но совершенно непонятен компьютеру. Программа на таком языке называется исходным текстом и хранится во внешнем файле с расширением .pas.
Для перевода программы на язык низкого уровня, понятный исполнителю-компьютеру, существуют специальные программы-переводчики - компиляторы. Результатом работы компилятора (иными словами, результатом процесса компиляции) является исполняемый код, который записывается в файл с расширением .exe.
Свойства алгоритма
Любой алгоритм должен обладать следующими свойствами:
- массовостью (алгоритм должен уметь решать не одну конкретную задачу, а целый класс однотипных задач);
- результативностью (алгоритм должен выдавать результат своей работы);
- определенностью (на каждом шаге выполнения алгоритма исполнитель должен точно знать, какой шаг будет следующим).
Эти же свойства присущи и программам, реализующим алгоритмы. Если же хотя бы одно из них оказывается невыполненным, программа полностью теряет смысл.
Схема алгоритма
Схема алгоритма это графический способ описания алгоритма, который базируется на использовании совокупности специальных символов (графических блоков) для изображения алгоритмов.
В схеме алгоритма каждому действию соответствует геометрическая фигура определенной конфигурации, представляемая в виде блочного символа (блока). Блоки соединяются линиями переходов, которые определяют порядок выполнения действия.
В таблице 1.1 приведены наиболее часто употребляемые блоки при построении схем алгоритмов. Внутри блоков указывается информация о выполняемых действиях.
Таблица 1.1
|
ОБОЗНАЧЕНИЕ |
НАИМЕНОВНИЕ |
ПРИМЕЧАНИЕ |
|||
|
|
Терминатор |
Начало,
конец, останов |
|||
|
|
Ввод-вывод данных |
Мы будем использовать этот символ только для обозначения ввода |
|||
|
|
Процесс |
Используется для указания вычислительных действий |
|||
|
|
Ввод с клавиатуры |
Используется для указания действий по вводу данных |
|||
|
|
Дисплей |
|
|||
|
|
Решение |
Разветвление (альтернативное решение) |
|||
|
|
Начало цикла ö ½ ý ½ ø Конец цикла
|
Границы цикла |
|||
|
8
|
Предопределенный процесс |
Вычисление по подпрограмме |
|||
|
9
|
Документ |
Вывод, печать на бумаге (принтере) |
|||
|
|
Соединитель |
Используется ,когда необходим разрыв линий потока |
|||
|
|
Комментарий |
Запись пояснений |
Схемы алгоритмов могут быть:
- укрупненными;
- детализированными.
В первом случае схема помогает нагляднее выделить логику алгоритма.
Во втором случае при программировании каждому блоку алгоритма ставится в соответствие определённый оператор алгоритмического языка. Это упрощает процесс составления программ.
В процессе решения задач, как правило, встречаются алгоритмы следующих вычислительных структур:
- линейной;
- разветвляющейся;
- циклической.
Каждая из этих структур имеет свои специфические приемы построения.
Методику построения схем алгоритмов проиллюстрируем примерами.
Пример 1 (алгоритм линейной структуры).
По заданным значениям 3-х сторон треугольника:
а=2,5; b=5,42; с=7,85
построить схему машинного алгоритма вычисления его площади.
Решение
1. Выделяем математический аспект задачи, т. е. определим формулы, по которым должны выполняться вычисления (математический алгоритм).
В данном случае используем в качестве алгоритма формулу Герона:
,
где
.
2. Логика алгоритма сводится к простой линейной структуре. Такой порядок последовательного выполнения действий называется естественным. В соответствие с логикой алгоритма соединяем блоки между собой. Поскольку стандартным направлением потока информации является направление сверху вниз и слева направо, то такое направление в схемах стрелками не отмечается.
|
|
Рисунок 1.1 Схема алгоритма к примеру 1
Пример 2 (алгоритм разветвляющийся вычислительной структуры).
Построить
схему машинного алгоритма
решения квадратного уравнения
.
Решение.
1. Математический аспект задачи:
.
Далее:
а)
если d > 0,
то 
;
б) если
d = 0,
то 
;
в) если d < 0, то должно быть сообщение «корни комплексные».
2. В этой задаче логика алгоритма требует проверок d, т. е. построение разветвлений, что нарушает естественный порядок выполняемых действий. Поэтому структура алгоритма здесь является разветвляющейся. Направление потока (снизу вверх и справа налево) отмечается стрелками.
|
|
Рисунок 1.2 Схема алгоритма к примеру 2
Пример 3 (алгоритм циклической вычислительной структуры).
Построить схему машинного алгоритма решения следующей задачи:
; 
.
Предполагается,
что числовые значения переменных 
, 
и 
должны быть заданы:
Решение.
1. Математический аспект задачи представлен формулой, т. е. постановкой задачи.
2. Из постановки следует, что логика алгоритма требует организации повторений т. е. циклов от i = 1 до i = n.
Рисунок 1.3 Схема алгоритма к примеру 3
Компиляция, отладка и тестирование
Никто не станет спорить с тем, что неграмотно написанный текст очень сложно, а порой и вовсе невозможно правильно перевести на другой язык. Это верно для естественных языков, это верно и для языков программирования. Но если переводчик-человек иногда может как-то догадаться, что же именно хотел сказать автор неграмотного текста, то программе-переводчику такое не по силам. Любой компилятор требует, чтобы программа, подаваемая ему для перевода, была абсолютно правильно составлена.
В языке программирования, как и в любом другом языке, существуют синтаксис - правила записи его конструкций - и семантика - смысл его конструкций. Компилятор проверяет только синтаксис. Поиском же семантических ошибок занимается программист в процессе тестирования и отладки своей программы
Отладка - это поиск и исправление ошибок в программе. Тестирование - это составление специальных наборов входных и выходных данных (тестов), а затем исполнение программы и проверка полученных результатов в поисках возможных семантических или логических ошибок.
Средства разработки программ
Существует довольно большое количество средств написания программ на языке Pascal, позволяющих составлять, компилировать, исполнять и отлаживать программы на этом удобном языке структурного программирования. Самыми известными сегодня являются Turbo Pascal (он же Borland Pascal), Object Pascal (не путать с Delphi) и Free Pascal. Мы будем работать в самой распространенной (хотя и не во всем соответствующую стандартам ISO) реализацией - Turbo Pascal.
Итак, в составе среды разработчика Turbo Pascal имеются:
- текстовый редактор, в котором можно набирать тексты программ;
- компилятор, превращающий исходные тексты в исполняемый код;
- отладчик, помогающий обнаруживать и исправлять ошибки в программе.